from typing import List


class SegmentTree:
    """
    8-3线段树
    """
    def __init__(self, a: List[int]):
        n = len(a)
        self.max = [0] * (2 << (n - 1).bit_length())
        #线段树从1开始，0舍弃
        self.build(a, 1, 0, n - 1)
        print(self.max)

    def maintain(self, o: int):
        """
        非叶子节点计算当前节点值(左右节点取最大)
        :param o: 非叶子节点索引
        :return: 当前节点的值(左右节点取最大)
        """
        self.max[o] = max(self.max[o * 2], self.max[o * 2 + 1])

    # 初始化线段树
    def build(self, a: List[int], o: int, l: int, r: int):
        """
        构建线段树
        :param a: 原数组
        :param o: 线段树索引
        :param l: 原数组左区间
        :param r: 原数组右区间
        :return:
        """
        #说明当前没有其他数只有一个数，则认为是叶子节点，直接赋值返回
        if l == r:
            self.max[o] = a[l]
            return
        m = (l + r) // 2
        self.build(a, o * 2, l, m) #计算左边
        self.build(a, o * 2 + 1, m + 1, r) #计算右边
        self.maintain(o)#左右计算完，比较当前最大值

    # 找区间内的第一个 >= x 的数，并更新为 -1，返回这个数的下标（没有则返回 -1）
    def find_first_and_update(self, o: int, l: int, r: int, x: int) -> int:
        if self.max[o] < x:  # 区间没有 >= x 的数
            return -1
        if l == r:
            self.max[o] = -1  # 更新为 -1，表示不能放水果
            return l
        m = (l + r) // 2
        i = self.find_first_and_update(o * 2, l, m, x)  # 先递归左子树
        if i < 0:  # 左子树没找到
            i = self.find_first_and_update(o * 2 + 1, m + 1, r, x)  # 再递归右子树
        self.maintain(o)
        return i
if __name__ == '__main__':
    # s = SegmentTree([5, 4, 3, 4, 7, 9, 8, 4])
    # print(s.query(0,2))
    s = SegmentTree([9,9,9,9,9])
